Line-thinning is a technique frequently used as a preprocessing procedure in electronic image processing, and various line-thinning processes have been developed up to now. Background information on these processes may be found in the articles, Tamura: "Comparative Study of Line-Thinning Schemes", Material of IP Study Group of Information Processing Society of Japan (1975-06) and Tamura: "Studies of Line-Thinning Schemes", Material of PRL Study Group of the Institute of Electronics and Communication Engineers of Japan, PRL 75-66, which compare and study line-thinning processes in general.
Particular techniques for line-thinning include sequential and parallel processes. Sequential line-thinning processes are described in, for example, the following material:
J. Hilditch: "Linear Skeleton from Square Cupboards", In Machine Intelligence IV, B. Meltzer and D. Michie, Eds. University Press, Edinburgh, pp. 403-420 (1969).
E. S. Duetsch: "Computer Similation of a Character-Recognition Machine, Part 1 ", The Post Office Electrical Engineers J. 60, pp. 39-44 (April, 1967); and
Yokoi et al: "An Analysis of Topological Features at Digitized Binary Pictures using Local Features", CG and IP, Vol. 4, No. 1, pp. 63-73 (March, 1975).
Parallel line-thinning processes are indicated in, for example, the following material:
D. Rutoritz: "Pattern Recognition", J. Royal Statist. Soc. 129, Series A, pp. 504-430 (1966); and
Tamura and Mori: "Agorithm and Connectivity of Parallel Line-Thinning of Binary Figures", National Communication Conference in 1974, No. 1539, p. 1390.
A further line-thinning method that processes a picture by segmenting it into a plurality of rectangular areas is disclosed in Japanese Laid-Open Patent Specification No. 163078/83.
The conventional line-thinning process has the following problems.
As will be seen from the line-thinning process of Hilditch, since one scanning for an entire picture reduces the width of lines in the picture by one pixel from each side, the number of scannings to be repeated for the entire picture is about W/2 where W is the maximum line width contained in the picture. This is illustrated in FIGS. 3A-3D. In this case, the number of scanning points P required for line-thinning is: ##EQU1## where S is the number of scanning points in an entire picture(I.times.J); EQU W/2
is the repeated number of scannings of the entire picture; and
W is the maximum line width in the entire picture.
It will be seen that even if there is only one area with a thick line or a solid black area in the picture, it is required to repeatedly scan the entire picture because of such an area, which, will take an enormous amount of processing time.
Thus, to reduce the processing time, the previously-cited Japanese Laid-Open Patent Specification No. 163078/83 proposes to increase the speed of line-thinning by segmenting the picture into a plurality of rectangular areas so as to quickly complete the processing for the segmented areas without thick lines, and to repeatedly scan only the segmented areas with thick lines.
However, there still remains the problem that many unnecessary scannings are performed because, even in such segmented areas, the ratio of the lines to the overall area is often only a small percentage.
In addition, in the sequential line-thinning method of Hilditch, when the segmentation into rectangular areas is employed, each segmented area cannot be processed independently so to assure connectivity at a boundary. This means that each segmented area cannot be processed in parallel.